package com.mrzhou.study.struct.linked;

/**
 * 数据结构之单向链表, 以下代码实现对链表的增删改查的操作
 *      单向链表的结构:
 *          每个链表节点都分为两块区域: 数据域 + 指针域;
 *              数据域: 存储数据
 *              指针域: 存储下一节点的引用地址
 * @author 隆冬寒梅
 */
public class SinglyLinkedList<T> {

    private transient Node<T> header = new Node<>(); // 预定义链表的头部节点, 链表的实际起始位置应该是headerNode.next
    private transient int size = 0; // 用以统计链表的节点数量

    /**
     *  在链表的指定位置插入
     */
    public void add(int index, T data) {
        checkPositionIndex(index);
        if(index == size) { // index为零表示当前数据要插入到头部
            addLast(data);
            return; // 及时结束, 防止size统计错误
        }

        // 获取当前index的上一个对应的节点
        Node<T> currentNode = this.header; // 首先获取当前链表的第一个节点
        int i = 0;
        while (currentNode.next != null && i != index) { // 因为要遍历整个链表, 所以时间复杂度为O(n)
            currentNode = currentNode.next;
            i++;
        }
        // 创建一个新的节点 并 将上一个节点的nextCode的指针也就是index当前对应的节点
        Node node = new Node(data, currentNode.next);
        currentNode.next = node;
        size++;
    }

    public void addFirst(T data) {
        if(isEmpty()) {
            this.header.next = new Node<>(data, null);
        } else {
            Node node = new Node(data, this.header.next);
            this.header.next = node;
        }
        size++;
    }

    public void addLast(T data) {
        if(isEmpty()) {
            this.header.next = new Node<>(data, null);
        } else {
            int i = 0;
            Node current = this.header.next;
            while(current.next != null) {
                current = current.next;
                i++;
            }
            current.next = new Node(data, null);
        }
        size++;
    }

    /**
     * 删除指定下标的元素(节点)
     * @param index
     */
    public void remove(int index) {
        checkElemIndex(index);
//        if(index == 0) {
//            removeFirst(); return;
//        }
        Node current = this.header; // 链表的开始节点
        int i = 0;
        while (current.next != null && i != index) {
            current = current.next;
            i++;
        }
        Node remove = current.next;
        current.next = remove.next;
        remove.next = null;
        size--;
    }

    public void removeFirst() {
        if(!isEmpty()) {
            Node node = this.header.next;
            this.header.next = node.next;
            node.next=null;
            size--;
        }
    }

    /**
     * 获取链表index的元素
     * @param index
     * @return
     */
    public T get(int index) {
        checkElemIndex(index);
        if(isEmpty()) {
            return null;
        } else {
            Node<T> current = this.header.next;
            int i = 0;
            while (current.next != null && i != index) {
                current = current.next;
                i++;
            }
            return current.data;
        }
    }

    public static void main(String[] args) {
        SinglyLinkedList<Integer> linkedList = new SinglyLinkedList();
        linkedList.add(0, 34);
        linkedList.addLast(100);
        linkedList.addLast(99);
        linkedList.addLast(98);
        System.out.printf("从尾部插入####\n共有元素: %d个\n元素信息: %s\n", linkedList.size, linkedList);
        linkedList.add(0, -1);
        linkedList.remove(0);
        linkedList.addFirst(0);
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.add(2, 4);
        linkedList.add(0, 5);
        linkedList.add(5, 6);
        linkedList.addLast(-2);
        linkedList.addLast(-10);
        linkedList.add(10, 12);
        System.out.printf("删除前####\n共有元素: %d个\n元素信息: %s\n", linkedList.size, linkedList);
        linkedList.remove(8);
        linkedList.remove(0);
        System.out.printf("删除后####\n共有元素: %d个\n元素信息: %s\n", linkedList.size, linkedList);
        System.out.printf("index = %d 的元素为: %d\n", 9,  linkedList.get(9));
    }

    public void checkPositionIndex(int index) {
        if(!isPositionIndex(index)) {
            throw new ArrayIndexOutOfBoundsException(String.format("超过当前链表的最大长度, 链表最大索引: %d\t入参索引: %d",  size -1 ,  index));
        }
    }

    public void checkElemIndex(int index) {
        if(!isElemIndex(index)) {
            throw new ArrayIndexOutOfBoundsException(String.format("超过当前链表的最大长度, 链表最大索引: %d\t入参索引: %d",  size -1 ,  index));
        }
    }

    private boolean isPositionIndex(int index) {
        return index >=0 && index <= size;
    }

    private boolean isElemIndex(int index) {
        return index >=0 && index < size;
    }

    public boolean isEmpty() {
        return this.header.next == null;
    }

    public int size(){
        return this.size;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        Node currentNode = this.header.next;
        while(currentNode != null) {
            if(currentNode.next == null) {
                sb.append(currentNode.data).append("]");
            } else {
                sb.append(currentNode.data).append(", ");
            }
            currentNode = currentNode.next;
        }
        return sb.toString();
    }


    private class Node<T> {
        T data; // 链表节点保存的数据, 这里叫数据域
        Node<T> next;// 链表下一节点的引用, 这里叫指针域

        public Node(){ }

        public Node(T data, Node nextNode) {
            this.data = data;
            this.next = nextNode;
        }

        @Override
        public String toString() {
            if(data == null) {
                return "";
            }
            return data.toString();
        }
    }

}
